// Copyright 2015 the V8 project authors. All rights reserved.
// Use of this source code is governed by a BSD-style license that can be
// found in the LICENSE file.

#ifndef V8_IDENTITY_MAP_H_
#define V8_IDENTITY_MAP_H_

#include "src/base/functional.h"
#include "src/handles.h"
#include "src/objects/heap-object.h"

namespace v8 {
namespace internal {

    // Forward declarations.
    class Heap;

    // Base class of identity maps contains shared code for all template
    // instantions.
    class V8_EXPORT_PRIVATE IdentityMapBase {
    public:
        bool empty() const { return size_ == 0; }
        int size() const { return size_; }
        int capacity() const { return capacity_; }
        bool is_iterable() const { return is_iterable_; }

    protected:
        // Allow Tester to access internals, including changing the address of objects
        // within the {keys_} array in order to simulate a moving GC.
        friend class IdentityMapTester;

        typedef void** RawEntry;

        explicit IdentityMapBase(Heap* heap)
            : heap_(heap)
            , gc_counter_(-1)
            , size_(0)
            , capacity_(0)
            , mask_(0)
            , keys_(nullptr)
            , values_(nullptr)
            , is_iterable_(false)
        {
        }
        virtual ~IdentityMapBase();

        RawEntry GetEntry(Address key);
        RawEntry FindEntry(Address key) const;
        bool DeleteEntry(Address key, void** deleted_value);
        void Clear();

        Address KeyAtIndex(int index) const;

        RawEntry EntryAtIndex(int index) const;
        int NextIndex(int index) const;

        void EnableIteration();
        void DisableIteration();

        virtual void** NewPointerArray(size_t length) = 0;
        virtual void DeleteArray(void* array) = 0;

    private:
        // Internal implementation should not be called directly by subclasses.
        int ScanKeysFor(Address address) const;
        int InsertKey(Address address);
        int Lookup(Address key) const;
        int LookupOrInsert(Address key);
        bool DeleteIndex(int index, void** deleted_value);
        void Rehash();
        void Resize(int new_capacity);
        int Hash(Address address) const;

        base::hash<uintptr_t> hasher_;
        Heap* heap_;
        int gc_counter_;
        int size_;
        int capacity_;
        int mask_;
        Address* keys_;
        void** values_;
        bool is_iterable_;

        DISALLOW_COPY_AND_ASSIGN(IdentityMapBase);
    };

    // Implements an identity map from object addresses to a given value type {V}.
    // The map is robust w.r.t. garbage collection by synchronization with the
    // supplied {heap}.
    //  * Keys are treated as strong roots.
    //  * The value type {V} must be reinterpret_cast'able to {void*}
    //  * The value type {V} must not be a heap type.
    template <typename V, class AllocationPolicy>
    class IdentityMap : public IdentityMapBase {
    public:
        explicit IdentityMap(Heap* heap,
            AllocationPolicy allocator = AllocationPolicy())
            : IdentityMapBase(heap)
            , allocator_(allocator)
        {
        }
        ~IdentityMap() override { Clear(); }

        // Searches this map for the given key using the object's address
        // as the identity, returning:
        //    found => a pointer to the storage location for the value
        //    not found => a pointer to a new storage location for the value
        V* Get(Handle<Object> key) { return Get(*key); }
        V* Get(Object key) { return reinterpret_cast<V*>(GetEntry(key.ptr())); }

        // Searches this map for the given key using the object's address
        // as the identity, returning:
        //    found => a pointer to the storage location for the value
        //    not found => {nullptr}
        V* Find(Handle<Object> key) const { return Find(*key); }
        V* Find(Object key) const
        {
            return reinterpret_cast<V*>(FindEntry(key.ptr()));
        }

        // Set the value for the given key.
        void Set(Handle<Object> key, V v) { Set(*key, v); }
        void Set(Object key, V v)
        {
            *(reinterpret_cast<V*>(GetEntry(key.ptr()))) = v;
        }

        bool Delete(Handle<Object> key, V* deleted_value)
        {
            return Delete(*key, deleted_value);
        }
        bool Delete(Object key, V* deleted_value)
        {
            void* v = nullptr;
            bool deleted_something = DeleteEntry(key.ptr(), &v);
            if (deleted_value != nullptr && deleted_something) {
                *deleted_value = *reinterpret_cast<V*>(&v);
            }
            return deleted_something;
        }

        // Removes all elements from the map.
        void Clear() { IdentityMapBase::Clear(); }

        // Iterator over IdentityMap. The IteratableScope used to create this Iterator
        // must be live for the duration of the iteration.
        class Iterator {
        public:
            Iterator& operator++()
            {
                index_ = map_->NextIndex(index_);
                return *this;
            }

            Object key() const { return Object(map_->KeyAtIndex(index_)); }
            V* entry() const
            {
                return reinterpret_cast<V*>(map_->EntryAtIndex(index_));
            }

            V* operator*() { return entry(); }
            V* operator->() { return entry(); }
            bool operator!=(const Iterator& other) { return index_ != other.index_; }

        private:
            Iterator(IdentityMap* map, int index)
                : map_(map)
                , index_(index)
            {
            }

            IdentityMap* map_;
            int index_;

            friend class IdentityMap;
        };

        class IteratableScope {
        public:
            explicit IteratableScope(IdentityMap* map)
                : map_(map)
            {
                CHECK(!map_->is_iterable());
                map_->EnableIteration();
            }
            ~IteratableScope()
            {
                CHECK(map_->is_iterable());
                map_->DisableIteration();
            }

            Iterator begin() { return Iterator(map_, map_->NextIndex(-1)); }
            Iterator end() { return Iterator(map_, map_->capacity()); }

        private:
            IdentityMap* map_;
            DISALLOW_COPY_AND_ASSIGN(IteratableScope);
        };

    protected:
        void** NewPointerArray(size_t length) override
        {
            return static_cast<void**>(allocator_.New(sizeof(void*) * length));
        }
        void DeleteArray(void* array) override { allocator_.Delete(array); }

    private:
        AllocationPolicy allocator_;
        DISALLOW_COPY_AND_ASSIGN(IdentityMap);
    };

} // namespace internal
} // namespace v8

#endif // V8_IDENTITY_MAP_H_
